/**
 * @(#) LCA.java Apr 3, 2010 8:42:21 PM
 * Copyright (C) 2009 GeeYee Inc. 60606, Chicago, IL, USA
 * All right reserved
 */
package tree;

import java.util.Stack;


/**
 *
 * Class <code>LCA</code>
 * 
 * @author Xiaowen dingxwsimon@gmail.com
 * @since Apr 3, 2010 8:42:21 PM
 * 
 */
public class LCA
{
  //best one, O(n)
  public static Node LCABT(Node root,int val1,int val2){
    if(root == null) return null;
    if(root.value == val1 || root.value == val2)
      return root;
    Node left = LCABT(root.left, val1, val2);
    Node right = LCABT(root.right, val1, val2);
    if(left != null && right != null)//&& ((left.value == val1 && right.value == val2) || (left.value == val2 && right.value == val1)))
      return root;
    return left != null ? left : right;
  }  
	
	public static Node LCABST(Node root,int val1,int val2)
	{
	    if(root == null) return null;
	    Node curr = root;
	    Node par = root;
	    while(curr != null)
	    {
	 
	       if(curr.value < val1 && curr.value < val2)
	       {
	        par = curr;
	        curr = curr.right;
	       }
	       else if(curr.value >val1 && curr.value >val2)
	       {
	        par = curr;
	        curr = curr.left;
	       }
	       else{
	             return curr;
	           }
	 
	    }
	    return null;
	 
	}
	
	public static class Result {
	  public Node node;
	  public boolean isAncestor;
	  public Result(Node n, boolean isAnc){
	    node = n;
	    isAncestor = isAnc;
	  }
	}
	
	Result helper(Node root, int p, int q){
	  if(root == null)
	    return new Result(null, false);
	  if(root.value == p && root.value == q)
	    return new Result(root, true);
	  Result rx = helper(root.left, p,q);
	  if(rx.isAncestor){
	    return rx;
	  }
	  
	  Result ry = helper(root.right, p, q);
	  if(ry.isAncestor){
	    return ry;
	  }
	  
	  if(rx.node != null && ry.node != null){
	    return new Result(root, true);
	  } else if(root.value == p || root.value == q){
	    boolean isAnc = rx.node != null || ry.node != null ? true : false;
	    return new Result(root, isAnc);
	  } else {
	    return new Result(rx.node != null ? rx.node : ry.node, false);
	  }
	}
	
	
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

    System.out.println(LCA.LCABT(Node.create1(), 7, 11).value);

  }

}
